package wikisearch.graphalgorithms;

import java.util.*;

import org.jgrapht.alg.EdmondsKarpMaximumFlow;

import wikisearch.datastructures.Graph;
import wikisearch.datastructures.WEdge;

public class MinCut {

	public static double mincut(HashSet<WEdge> mincut, EdmondsKarpMaximumFlow<String, WEdge> maxflow, 
			Map<WEdge, Double> flowVals, Graph g, HashSet<String> cluster1, HashSet<String> cluster2) {

		mincut = new HashSet<WEdge>();
		
		HashMap<WEdge, Double> fullcaps = new HashMap<WEdge, Double>();
		double fullCapSum = 0.0;
		for (WEdge e : flowVals.keySet()) {
			
			if (g.getEdgeWeight(e) <= flowVals.get(e).doubleValue()
					&& g.getEdgeWeight(e) >= flowVals.get(e).doubleValue()) {
				fullcaps.put(e, flowVals.get(e));
				fullCapSum += flowVals.get(e).doubleValue();
			} 
		} //this for-loop gets all edges that are full capacity

		detectCluster(mincut, fullcaps, maxflow, g, cluster1, cluster2);
		return maxflow.getMaximumFlowValue().doubleValue();
	}

	private static void detectCluster(HashSet<WEdge> mincut,
			HashMap<WEdge, Double> fullcaps, EdmondsKarpMaximumFlow<String, WEdge> maxflow, Graph g,
			HashSet<String> cluster1, HashSet<String> cluster2) {
		
		Stack<String> exploreNodes = new Stack<String>();
		exploreNodes.add(maxflow.getCurrentSource());
		HashSet<String> seenNodes = new HashSet<String>();
		HashSet<WEdge> seenEdges = new HashSet<WEdge>();
		
		dfs(mincut, fullcaps, g, exploreNodes, seenNodes, seenEdges); //all nodes in 'seenNodes' are in cluster 0, otherwise in cluster1.

		for (String n : seenNodes) {
			cluster1.add(n);
		}
		graphComplement(g, cluster1, cluster2);
		
		for (WEdge e : fullcaps.keySet()) {
			String s = g.getEdgeSource(e);
			String t = g.getEdgeTarget(e);
			if ( (cluster1.contains(s) && cluster2.contains(t))
				|| (cluster2.contains(s) && cluster1.contains(t)) ) {
				mincut.add(e);
			}
		}
	}

	/*
	 * Takes out nodes in cluster1 from graph g.
	 */
	private static void graphComplement(Graph g,
			HashSet<String> cluster1, HashSet<String> cluster2) {

		for (String s : g.vertexSet()) {
			
			if (!cluster1.contains(s)) {
				cluster2.add(s);
			}
		}
	}

	private static void dfs(HashSet<WEdge> mincut, HashMap<WEdge, Double> fullcaps, Graph g, Stack<String> exploreNodes,
			HashSet<String> seenNodes, HashSet<WEdge> seenEdges) {
		
		while (exploreNodes.size() > 0) {
			String currNode = exploreNodes.pop();
			seenNodes.add(currNode);
			Set<WEdge> incident = g.edgesOf(currNode);
			
			for (WEdge e : incident) {
				if (g.getEdgeSource(e).equals(currNode) && 
						!seenEdges.contains(e) && fullcaps.get(e) == null) { //fullcaps.get(e).doubleValue() < g.getEdgeWeight(e)) {
					seenEdges.add(e);
					String s = g.getEdgeSource(e);
					String t = g.getEdgeTarget(e);
					if (!seenNodes.contains(s)) {
						exploreNodes.push(s);
					}
					if (!seenNodes.contains(t)) {
						exploreNodes.push(t);
					}
				}
			}
		} 
	}
}
